package com.ljy.my_study.leetcode.全排列;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lijunying
 * @date 2021/8/23 11:24
 */
public class TestMain {

//    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
//
//             
//
//    示例 1：
//
//    输入：nums = [1,2,3]
//    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//    示例 2：
//
//    输入：nums = [0,1]
//    输出：[[0,1],[1,0]]
//    示例 3：
//
//    输入：nums = [1]
//    输出：[[1]]
//             
//
//    提示：
//
//            1 <= nums.length <= 6
//            -10 <= nums[i] <= 10
//    nums 中的所有整数 互不相同
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/permutations
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(new TestMain().permute(new int[]{1,2,3}));
    }

    public List<List<Integer>> permute(int[] nums) {
        int len=nums.length;
        boolean[] visited=new boolean[len];
        List<List<Integer>> result=new ArrayList<>();
        dfs(nums,new ArrayList<>(),visited,result);
        return result;
    }

    private void dfs(int[] nums, List<Integer> list, boolean[] visited, List<List<Integer>> result){
        int len=nums.length;
        if(list.size()>=len){
            result.add(list);
            return;
        }
        for(int i=0;i<len;i++){
            if(visited[i]){
                continue;
            }
            visited[i]=true;
            List<Integer> newList=new ArrayList<>(list);
            newList.add(nums[i]);
            dfs(nums,newList,visited,result);
            visited[i]=false;
        }
    }
}
